package com.leetcode.questiononehundardandfifty.数组;

import java.util.*;

/**
 * @author wtcode
 * @Description
 * @date 2025/4/3 - 9:22
 */
public class Answer {
    public static void main(String[] args) {
        //int[] nums1 = new int[]{1,2,3,0,0,0};
        //int[] nums2 = new int[]{2,5,6};
        //merge(nums1,3,nums2,3);

        //int[] array = {3, 2, 2, 3};
        //removeElement(array,3);

        //int[] array = {1,1};
        //removeDuplicates(array);
        int[] array = {2,3,1,1,4};
        jump(array);

    }
    // 在原数组基础上合并数组，需要用到额外的存贮数组
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0;
        int p2 = 0;
        int cur = 0;
        int[] newarr = new int[m+n];

        while (p1 < m || p2 < n){
            if(p1 == m){
                cur = nums2[p2++];
            }else if(p2 == n){
                cur = nums1[p1++];
            }else if (nums1[p1] <= nums2[p2]){
                cur = nums1[p1++];
            }else {
                cur = nums2[p2++];
            }
            newarr[p1+p2-1] = cur;
        }

        for (int i = 0; i < newarr.length; i++) {
            nums1[i] = newarr[i];
        }

    }


    // 原地移除值为val的数组元素
    public static int removeElement(int[] nums, int val) {
        int i =0;
        for(int j = 0 ; j < nums.length ; j++){
            if(nums[j] != val){
                nums[i] = nums[j];
                i++;
            }
        }
        return i;
    }

    // 删除数组中的重复元素
    public static int removeDuplicates(int[] nums) {
        int slow =  1;
        int fast = 1;

        while (fast < nums.length){
            if(nums[fast] != nums[fast-1]){
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }

    // 删除数组中的重复元素2
    public static int removeDuplicates2(int[] nums) {
        int len = nums.length;
        int fast = 2;
        int slow = 2;
        while(fast < len){
            if(nums[slow-2] != nums[fast]){
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }

    // 多数元素
    public static int majorityElement(int[] nums) {
        int count = 0;
        int len = nums.length /2;
        Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
        for (int num : nums) {
            if (!counts.containsKey(num)) {
                counts.put(num, 1);
            } else {
                counts.put(num, counts.get(num) + 1);
            }
        }

        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() > len) {
                count = entry.getKey();
            }
        }
        return count;
    }

    // 轮转数组
    public static void rotate(int[] nums, int k) {
        int len = nums.length;
        int[] resNums = new int[len];
        for(int i = 0; i < len; i++){
            int index = (i + k) % len;
            resNums[index] = nums[i];
        }
        for(int i = 0; i <resNums.length; i++){
            nums[i] = resNums[i];
        }
    }

    // 买卖股票最佳时期
    public static int maxProfit(int[] prices) {
        int buy = Integer.MAX_VALUE;
        int profit = 0;
        for (int price : prices) {
            buy = Math.min(price,buy);
            profit = Math.max(profit,price-buy);
        }
        return profit;
    }

    // 买卖股票最佳时期二
    public static int maxProfit2(int[] prices) {
        int max = 0;
        for(int i = 1 ; i < prices.length; i++){
            int temp = prices[i] - prices[i-1];
            if(temp > 0){
                max += temp;
            }
        }
        return max;
    }

    // 跳跃游戏
    public static boolean canJump(int[] nums) {
        int maxRight = 0;
        for (int i = 0; i < nums.length; i++) {
            if(maxRight < i){
                return false;
            }
            maxRight = Math.max(maxRight,i + nums[i]);
        }
        return true;
    }

    // 跳跃游戏2
    public static int jump(int[] nums) {
        int end = 0;
        int maxPosition = Integer.MIN_VALUE;
        int count = 0;

        for (int i = 0; i < nums.length-1; i++) {
            maxPosition = Math.max(maxPosition,i+nums[i]);
            if(i == end){
                end = maxPosition;
                count++;
            }
        }
        return count;


    }

    // h指数
    public static int hIndex(int[] citations) {
        Arrays.sort(citations);
        int h = 0;
        int i = citations.length - 1;
        while (i > 0 && citations[i] > h){
            h++;
            i--;
        }
        return h;
    }

    // 除自身之外数组乘积
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] L = new int[len];
        int[] R = new int[len];

        L[0] = 1;
        R[len-1] = 1;
        int[] res = new int[len];

        for (int i = 1; i < nums.length; i++) {
            L[i] = nums[i-1] * L[i-1];
        }

        for (int i = len-2; i >=0; i--) {
            R[i] = nums[i+1] * R[i+1];
        }

        for (int i = 0; i < len; i++) {
            res[i] = L[i] * R[i];
        }
        return res;

    }

}
